package com.roc.learn.goodgoodstudy.algorithms;

/**
 * 二分查找
 * O(log n)
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] array = {1, 5, 9, 53, 99, 230};
        System.out.println("位置：" + BinarySearch(array, 53));
        System.out.println("位置：" + BinarySearch(array, 88));
    }

    /**
     * 教学
     * O(1)，常数时间
     * O(log n)，也叫对数时间，这样的算法包括二分查找。
     * O(n)，也叫线性时间，这样的算法包括简单查找。
     * O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
     * O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
     * O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
     */
    public static Integer BinarySearch(int[] array, int item) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            System.out.println(mid);
            int guess = array[mid];
            if (guess == item) {
                return mid;
            } else if (guess > item) {
                high = mid - 1;
            } else if (guess < item) {
                low = mid + 1;
            }
        }
        return null;
    }

    /**
     * 练习1
     * 假设有一个包含128个名字的有序列表，
     * 你要使用二分查找在其中查找一个名字，
     * 请问最多需要几步才能找到？
     *
     * log128=7
     *
     *
     * 练习2
     * 上面列表的长度翻倍后，最多需要几步？
     *
     * log256=8
     */


}
